package leetcode.listnode;

import leetcode.ListNode;
import leetcode.ListNodeUtil;

/**
 * @author Cheng Jun
 * Description: 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * <p>
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/partition-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/7/29 23:26
 * @see leetcode.interviewClassics.partition
 */
public class partition {

    public static void main(String[] args) {
        ListNode listNode = ListNodeUtil.getListNode(new int[]{1, 3, 0, 2});
        partition(listNode, 3);
    }

    private static ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode dummy = new ListNode(x - 1, head);
        // 最后一个小于x的节点
        ListNode lessX = dummy;
        ListNode pointer = dummy;
        while (pointer.next != null) {
            if (pointer.next.val < x) {
                if (pointer.next == lessX.next) {
                    lessX = lessX.next;
                    pointer = pointer.next;
                } else {
                    ListNode temp = pointer.next;
                    pointer.next = temp.next;
                    temp.next = lessX.next;
                    lessX.next = temp;
                    lessX = lessX.next;
                }
            }else {
                pointer = pointer.next;
            }
        }
        return dummy.next;
    }
}
